//
// Created by 31897 on 2021/10/21.
//
template<class Type>
int BinarySearch(Type a[], const Type& x, int n) {
    int left = 0;
    int right = n - 1;
    while (left < right) {
        int middle = (left + right) / 2;
        if (x == a[middle])
            return middle;
        if (x > middle)
            left = middle + 1;
        else
            right = middle - 1;
    }
    return left;//返回left当left大于要查找的值，则left-1和left就是要的值
}
